﻿#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

/////25.模板⼀维前缀和
//int main()
//{
//    //输入数据;
//    int n, q;
//    cin >> n >> q;
//    vector<int> arr(n + 1);
//    for (int i = 1; i < n + 1; i++)  cin >> arr[i];
//    //生成一个前缀和数组;
//    vector<long long> dp(n + 1);
//    for (int i = 1; i < n + 1; i++)
//    {
//        dp[i] = dp[i - 1] + arr[i];
//    }
//    //输出结果;
//    int l=0, r=0;
//    while (q--)
//    {
//        cin >> l >> r;
//        cout << dp[r] - dp[l - 1] << endl;
//    }
//    return 0;
//}
//
////二维前缀和：
//#include <iostream>
//using namespace std;
//const int N = 1010;
//int arr[N][N];
//long long dp[N][N];
//int n, m, q;
//int main()
//{
//    cin >> n >> m >> q;
//    // 读⼊数据 
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> arr[i][j];
//    // 处理前缀和矩阵 
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
//    // 使⽤前缀和矩阵 
//    int x1, y1, x2, y2;
//    while (q--)
//    {
//        cin >> x1 >> y1 >> x2 >> y2;
//        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
//    }
//}



//寻找数组的中⼼下标（easy）
//////////自己写的代码;
//int pivotIndex(vector<int>& nums)
//{
//    int size = nums.size();
//    vector<int>dp(size, 0);
//    for (int i = 0; i < size; i++)
//    {
//        if (i == 0)
//            dp[i] = nums[i];
//        else
//            dp[i] = dp[i - 1] + nums[i];
//    }
//    for (int i = 0; i < size; i++)
//    {
//        if (i == 0)
//        {
//            if (dp[size - 1] - dp[i] == 0)
//                return 0;
//        }
//        else
//        {
//            if (dp[i - 1] == dp[size - 1] - dp[i])return i;
//        }
//    }
//    return -1;
//}
//////////////////////前缀和优化版本
//int pivotIndex(vector<int>& nums)
//{
//    int size = nums.size();
//    vector<int> f(size);
//    vector<int> g(size);
//    for (int i = 1; i < size; i++) f[i] = f[i - 1] + nums[i - 1];
//    for (int i = size - 2; i >= 0; i--)   g[i] = g[i + 1] + nums[i + 1];
//    for (int i = 0; i < size; i++) if (f[i] == g[i]) return i;
//    return -1;
//}


///////////////////28.除⾃⾝以外数组的乘积（medium）
//class Solution {
//public:
//    vector<int> productExceptSelf(vector<int>& nums)
//    {
//        int size = nums.size();
//        vector<int> f(size, 1);
//        vector<int> g(size, 1);
//        for (int i = 1; i < size; i++) f[i] = f[i - 1] * nums[i - 1];
//        for (int i = size - 2; i >= 0; i--) g[i] = g[i + 1] * nums[i + 1];
//        vector<int> ret(size);
//        for (int i = 0; i < size; i++)
//        {
//            ret[i] = f[i] * g[i];
//        }
//        return ret;
//    }
//};
///////////和为k的⼦数组（medium）
int subarraySum(vector<int>& nums, int k)
{
	unordered_map<int, int> hash; // 统计前缀和出现的次数 
	hash[0] = 1;
	int sum = 0, ret = 0;
	for (auto x : nums)
	{
		sum += x; // 计算当前位置的前缀和 
		if (hash.count(sum - k)) ret += hash[sum - k]; // 统计个数 
		hash[sum]++;
	}
	return ret;
}

int main()
{ 
	vector<int> nums{1, 2, 3};
	cout<<subarraySum(nums, 3);
	return 0;
}
